package LeetCode._06小算法;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/*
    1.给定字符串s,t,求出s是否包含t的全部字符的最小子串
    给定区间[left,right).左闭右开,这样right移动一位，[0,1)就包含一个元素，比[0,0]一开始就包含一个元素少很多麻烦

    需要两个map记录，一个needs记录t字符串每个字符出现的次数,window记录滑动窗口中t字符串字符出现的次数
    步骤:1:首先扫描字符串s,从左到右，直到包含字符串t的全部字符，找到一个可行解，不断扩大right的范围
         2:left不断逼近right,缩小子串的范围，直到t的字符串一个字符不在滑动窗口的范围，结束；

         重复上述过程，直到right到底s字符串的末尾
 */
public class _04滑动窗口 {
    private Map<Character,Integer> need = new HashMap<>(); //记录目标t字符串每个字符出现次数
    private Map<Character,Integer> window = new HashMap<>(); //记录滑动窗口中t字符串每个字符出现的次数
    public String minWindow(String s, String t) {
        if(s == null || t == null) return "";
        for (char c : t.toCharArray()) {
            //记录t字符串每个字符出现的次数
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0,right = 0; //滑动窗口,左闭右开[0,0)
        //其中 valid 变量表示窗口中满足 need 条件的字符个数
        //如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T。这时就可以开始收缩窗口，优化了
        int valid = 0;
        //记录最小覆盖子串的起始索引以及长度 [start,len)左闭右开
        int start = 0,len = Integer.MAX_VALUE; //len默认取最大
        while(right<s.length()){ //right直到字符串的最右侧
            char c = s.charAt(right); //c是移入窗口的字符
            right++; //右移right
            //如果存在该字符，那就对窗口进行更新数据
            if(need.containsKey(c)){ //该字符是t字符串中的字符
                window.put(c,window.getOrDefault(c,0)+1); //添加到窗口中
                if(window.get(c).equals(need.get(c))){ //滑动窗口字符出现的次数和need字符出现次数相等，说明一个字符已经找完
                    valid++;
                }
            }
            System.out.println("window:"+window);

            //判断左侧窗口是否需要收缩
            while(valid == need.size()){
                if(right - left < len){ //更新子串范围
                    //更新已经找到的子串范围 [start,len)左闭右开
                    start = left;
                    len = right - left;
                }
                char l =s.charAt(left); //l是将要移除窗口的字符
                left++; //左移窗口
                //进行窗口内数据的一系列更新
                if(need.containsKey(l)){ //need中包含字符l
                    if(window.get(l).equals(need.get(l))){ //说明该字符已经找到了，所以valid--
                        valid--;
                    }
                    //说明滑动窗口中l的字符多出现了一次，window的l字符出现的次数需要--
                    window.put(l,window.get(l)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len); //左闭右开截取
    }

    public static void main(String[] args) {
        _04滑动窗口 qw = new _04滑动窗口();
        final String s = qw.minWindow("EBBANCF", "ABC");
        System.out.println(s);
    }

}
